package com.example.arithmeticleetcode.learnArithmetic2.sort;


import java.util.Arrays;

/**
 * @program: arithmetic-leetcode
 * @description: 最好，最坏，平均时间复杂度为O(n+k) 空间复杂度
 * @author: FangZhen
 * @create: 2020-11-11 11:15
 **/
public class CountingSort extends Sort<Integer> {

    @Override
    protected void sort() {
        //求出最大值，最小值
        int max = array[0], min = array[0];
        for (int i = 1, len = array.length; i < len; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }

        //开辟内存空间，统计每个整数出现的次数
        int[] counts = new int[max - min + 1];

        //统计每个整数出现的次数
        for (int i = 0, len = array.length; i < len; i++) {
            counts[array[i] - min]++;
        }

        //累加次数
        for (int i = 1, len = counts.length; i < len; i++) {
            counts[i] += counts[i - 1];
        }

        //从后往前遍历元素，将他放到有序元素的合适位置
        int[] newArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {

            newArray[--counts[array[i] - min]] = array[i];
        }

        //将有序数组赋值到array
        for (int i = 0, len = newArray.length; i < len; i++) {
            array[i] = newArray[i];
        }

    }

    private void sort0() {
        //找出最大值
        int max = array[0];
        for (int i = 1, len = array.length; i < len; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }

        //开辟内存空间，统计每个整数出现的次数
        int[] counts = new int[max + 1];

        //统计每个整数出现的次数
        for (int i = 0, len = array.length; i < len; i++) {
            counts[array[i]]++;
        }

        //根据整数出现的次数对数组进行排序
        int index = 0;
        for (int i = 0, len = counts.length; i < len; i++) {
            for (int j = 0; j < counts[i]; j++) {
                array[index++] = i;
            }

        }
    }

    public static void main(String[] args) {
       Person[] persons = new Person[] {
               new Person(20, "A"),
               new Person(-13, "B"),
               new Person(17, "C"),
               new Person(12, "D"),
               new Person(-13, "E"),
               new Person(20, "F")
       };

        //求出最大值，最小值
        int max = persons[0].age, min = persons[0].age;
        for (int i = 1, len = persons.length; i < len; i++) {
            if (persons[i].age > max) {
                max = persons[i].age;
            }
            if (persons[i].age < min) {
                min = persons[i].age;
            }
        }

        //开辟内存空间，统计每个整数出现的次数
        int[] counts = new int[max - min + 1];

        //统计每个整数出现的次数
        for (int i = 0, len = persons.length; i < len; i++) {
            counts[persons[i].age - min]++;
        }

        //累加次数
        for (int i = 1, len = counts.length; i < len; i++) {
            counts[i] += counts[i - 1];
        }

        //从后往前遍历元素，将他放到有序元素的合适位置
        Person[] newArray = new Person[persons.length];
        for (int i = persons.length - 1; i >= 0; i--) {

            newArray[--counts[persons[i].age - min]] = persons[i];
        }

        //将有序数组赋值到array
        for (int i = 0, len = newArray.length; i < len; i++) {
            persons[i] = newArray[i];
            System.out.println(persons[i]);
        }



    }

    private static class Person{
        int age;
        String name;

        public Person(int age, String name) {
            this.age = age;
            this.name = name;
        }

        @Override
        public String toString() {
            return age + "    " + name;
        }
    }
}
